The present invention relates generally to computerized arithmetic operations, and specifically to finding a remainder after a computerized operation of division.
Computing systems frequently require a rounding-up or a rounding-down operation to be performed. For example, a multi-block transfer is described in a descriptor which typically comprises a header having an arbitrary number of doublewords, and 3 doublewords for each block of data transferred (a first doubleword giving a high address, a second doubleword giving a low address, and a third doubleword giving a length). The descriptor is written to a memory in which each line of the memory includes 3 doublewords. In order to determine how many lines of memory are needed, the total number of doublewords in the descriptor is rounded-up to the closest number which is a multiple of 3. To perform the rounding-up, a modulo-3 (mod-3) division of the number of doublewords in the descriptor is performed. Knowledge of the quotient and remainder of the division allows calculation of the required rounded-up number.
FIG. 1 is a schematic diagram of a finite state machine (FSM) 10 used to determine a mod-3 remainder after a division operation, as is known in the art. Machine 10 may be implemented as a hardware or software device, or as a combined hardware and software device, by methods known in the art. FSM 10 comprises a remainder 0 state 14, a remainder 1 state 16, and a remainder 2 state 18. Remainder 0 state 14 is set as an initial state. A binary number 12, herein assumed to be 11010 by way of example, is input to state 14, starting with its most significant digit (MSB). In a first cycle of FSM 10, since the MSB is 1, the state moves to remainder 1 state 16. Table I hereinbelow shows the states of FSM 10 as the binary digit is fed into the machine.
Table I shows that after 5 cycles, corresponding to the number of bits in number 12, FSM 10 halts at remainder 2 state, so that the remainder after dividing 11010 by a mod-3 division is +2. In general, for a binary number of length n, FSM 10 requires n cycles in order to determine the mod-3 remainder.
It is an object of some aspects of the present invention to provide a method and apparatus for determining a remainder after a modulo division of a binary number.
It is a further object of some aspects of the present invention to provide apparatus for determining a remainder requiring only one cycle of operation of the apparatus.
In preferred embodiments of the present invention, a modulo-n (mod-n) remainder of a binary number is determined, wherein n is a whole number greater than or equal to 2. The mod-n remainder is the value remaining after a mod-n division is performed on the number. The remainder is determined in a generator comprising a plurality of cells, each cell comprising n multiplexers. The plurality of cells corresponds to the number of bits in the binary number, and the multiplexer cells are coupled together in a linear sequence to form the generator. For each binary number input to the generator, the generator outputs an encoded value corresponding to the appropriate mod-n remainder in one cycle of operation of the generator. The ability to determine the mod-n remainder in one cycle significantly enhances the speed of remainder determination compared to methods known in the art.
There is therefore provided, according to a preferred embodiment of the present invention, apparatus for determining a remainder of a module division of a binary number made up of a string of bits, including:
a first plurality of substantially similar cells coupled in a linear sequence, the first plurality of cells including at least a first cell and a last cell, each cell of the first plurality including:
a second plurality of binary input terminals, the input terminals of the first cell being coupled to receive a pre-determined input;
a second plurality of binary output terminals, each coupled, except for the output terminals of the last cell, to a respective one of the input terminals of a subsequent cell in the sequence; and
a control input terminal, coupled to receive one of the bits in the string corresponding to a position of the cell in the sequence, so as to generate the remainder at the output terminals of the last cell in the sequence.
Preferably, the remainder is determined within one cycle of operation of the apparatus.
Preferably, each cell comprises a second plurality of multiplexers, wherein each multiplexer includes:
a first multiplexer input connected to one of the binary input terminals;
a second multiplexer input connected to another of the binary input terminals;
a multiplexer control input connected to the control input terminal; and
an output terminal connected to one of the binary output terminals and coupled to receive the first or the second multiplexer input responsive to a signal on the control input,
wherein each binary input terminal is connected to the first multiplexer input of one of the multiplexers and the second multiplexer input of another of the multiplexers, and each of the binary output terminals is connected to a respective one of the multiplexers.
Further preferably, the second plurality is three, and each of the first plurality of cells, given respective input values for a first one of the input terminals I0, a second one of the input terminals I1, a third one of the input terminals I2, and the control input terminal shown in the following table, a first one of the output terminals o0, a second one of the output terminals o1, and a third one of the output terminals o2 output values as shown in the table:
Preferably, the binary number includes a number of bit that is no more than a value of the first plurality.
Preferably, a module of the module division is equal to a value of the second plurality.
There is further provided, according to a preferred embodiment of the present invention, a method for determining a remainder of a module division of a binary number made up of a string of bits, including:
providing a first plurality of substantially similar cells, the first plurality of cells including at least a first cell and a last cell, each cell including a second plurality of binary input terminals and a second plurality of binary output terminals and a control input terminal;
coupling the cells in a linear sequence so that each of the binary output terminals of a cell in the sequence, except for the output terminals of the last cell, is connected to the respective binary input terminals of a subsequent cell in the sequence;
inputting a pre-determined input to the input terminals of the first cell;
inputting each bit of the string to the corresponding control input terminal of the cell in the sequence; and
generating the remainder at the output terminals of the last cell in the sequence.
Preferably, generating the remainder includes generating the remainder within one cycle of operation of the first plurality of cells.
Preferably, the binary number includes a number of bits that is no more than a value of the first plurality.
Further preferably, a modulo of the modulo division is equal to a value of the second plurality.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings, in which: